#include <bits/stdc++.h>

#define in read()
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define vec vector<int>
#define y1 y_____hahahaha_____1

using namespace std;

typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;

int read(){int x = 0,sgn = 1;char ch = getchar();for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;for(;isdigit(ch);ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48); return x * sgn;}

const int N = 310;
const int mod = 1e9 + 7;

void upd(int &x){x = x + (x >> 31 & mod);}

int n,a[N],fa[N];
int f[N][N][N];

int gf(int x){return x == fa[x] ? x : fa[x] = gf(fa[x]);}

void merge(int x,int y){x = gf(x),y = gf(y); if(x == y) return; fa[x] = y;}

bool can(ll x){ll t = sqrt(x); return t * t == x;}

int main(){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in; for(int i = 1;i <= n;i++) a[i] = in,fa[i] = i;
	for(int i = 1;i <= n;i++) for(int j = 1;j < i;j++) if(can((ll)a[i] * a[j])) merge(i,j);
	sort(fa + 1,fa + n + 1); f[0][0][0] = 1; int o = 0;
	for(int i = 1,ct = 0;i <= n;i++,o ^= 1){
		memset(f[o ^ 1],0,sizeof f[o ^ 1]);
		if(fa[i] ^ fa[i - 1]){
			ct = 0;
			for(int j = 0;j < i;j++){
				for(int k = 0;k <= j;k++) upd(f[o ^ 1][j][0] += (ll) f[o][j - k][k] * (i - j) % mod - mod);
				for(int k = 0;k <= j + 1;k++) upd(f[o ^ 1][j][0] += (ll) f[o][j - k + 1][k] * (j + 1) % mod - mod);
			}
		}else{
			for(int j = 0;j < i;j++){
				for(int k = 1;k <= ct;k++) upd(f[o ^ 1][j][k] += (ll) f[o][j][k - 1] * (ct * 2 - k + 1) % mod - mod);
				for(int k = 0;k <= ct;k++) upd(f[o ^ 1][j][k] += (ll) f[o][j + 1][k] * (j + 1) % mod - mod);
				for(int k = 0;k <= ct;k++) upd(f[o ^ 1][j][k] += (ll) f[o][j][k] * (i - ct * 2 + k - j) % mod - mod);
			}
		}ct++;
	}
	printf("%d\n",f[o][0][0]);
	return 0;
}
